W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Liczby Fibonacciego to ciąg liczb całkowitych zdefiniowany następująco: , , (dla ). Oto kilka pierwszych wyrazów tego ciągu: .
Wielki informatyk Bajtazar konstruuje niezwykły komputer. Liczby w tym komputerze są reprezentowane w układzie Fibonacciego. Liczby w takim układzie są reprezentowane jako ciągi zer i/lub jedynek (bitów), ciąg reprezentuje liczbę . (Zwróć uwagę, że nie korzystamy z ). Taka reprezentacja liczb nie jest niestety jednoznaczna, tzn. tę samą liczbę można reprezentować na wiele sposobów. Na przykład, liczbę można reprezentować jako: , lub . Dlatego też Bajtazar ograniczył się wyłącznie do reprezentacji spełniających następujące warunki:
Napisz program, który:
Na wejściu znajdują się reprezentacje Fibonacciego (spełniające podane powyżej warunki) dwóch dodatnich liczb całkowitych i - jedna w pierwszym, a druga w drugim wierszu. Każda z tych reprezentacji jest zapisana jako ciąg nieujemnych liczb całkowitych, pooddzielanych pojedynczymi odstępami. Pierwsza liczba w wierszu to długość reprezentacji , . Po niej następuje zer i/lub jedynek.
W pierwszym i jedynym wierszu wyjścia, Twój program powinien wypisać reprezentację Fibonacciego (spełniającą podane powyżej warunki) sumy . Tak jak to opisano dla wejścia, reprezentacja powinna mieć postać ciągu nieujemnych liczb całkowitych, pooddzielanych pojedynczymi odstępami. Pierwsza liczba w wierszu to długość reprezentacji , . Po niej następuje zer i/lub jedynek.
Dla danych wejściowych:
4 0 1 0 1 5 0 1 0 0 1
poprawną odpowiedzią jest:
6 1 0 1 0 0 1
Autor zadania: Marcin Kubica.